package com.company.笔试.二叉树的后序遍历序列;

/**
 * @ClassName Solution
 * @Description TODO
 *      输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 *      如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜索树）
 * @Author ylr
 * @Date 2021/8/16 23:47
 * @Version 1.0
 */
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence.length==0) return false;
        if (sequence.length==1) return true;
        return dfs(sequence,0,sequence.length-1);
    }

    //二叉搜索树得  左 < 根 <右
    //后序遍历得   左右根
    // 根节点 end   大于左子树的   找到第一个大于根节点的index就是右子树序列的第一个
    private boolean dfs(int[] sequence, int start, int end) {
        if (start>end) return true;// 若当前子树只有一个节点  start == end  只有一个节点[1]

        //1.从序列左边start开始找到左子树和右子树的边界  index
        int index = start;
        while (sequence[end]>sequence[index]&& index<end) index++;

        //2.index是右子树序列的第一个节点     end-1是右子树的根节点   右子树序列的节点都要比 根节点end大
        for (int i = index; i <end ; i++) {
            if (sequence[i]<sequence[end]) return  false;
        }

        //3.根节点鉴定完毕   递归左子树和右子树
  return  dfs(sequence,start,index-1)&&dfs(sequence,index,end-1);




    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.VerifySquenceOfBST(new int[]{4, 8, 6, 12, 16, 14, 10}));
    }
}
